$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Техника два показивача

Угнежђене петље обично подразумевају постојање две бројачке променљиве од којих спољашња само увећава своју вредност током итерације, док се вредност бројачке петље у унутрашњој увећава до неке горње границе, затим се поново враћа на неку доњу границу и поново увећава и то се понавља више пута, све док спољашња бројачка променљива не достигне своју максималну вредност. Ово по правилу доводи до квадратне сложености (тј. сложености вишег степена у случају угнежђавања већег броја петљи).

Техника два показивача обухвата широку класу ефикасних алгоритама које такође карактерише постојање две или више бројачких променљивих, које се крећу кроз елементе неког низа (често сортираног). Међутим, оно што је карактеристично за њих је то што се, за разлику од унутрашњих променљивих у угнежђеним петљама, ове променљиве стално “крећу у истом смеру”, тј. вредност им се или стално повећава или стално смањује (а честа је и комбинација где се “низ обилази са два краја”, где се једна променљива стално повећава, а друга стално смањује). Техничка реализација може бити било помоћу једне петље која контролише вредности обе променљиве, било помоћу угнежђених петљи, али тако да се након завршетка тела унутрашње петље, спољашња променљива увећава до места где се унутрашња петља завршила. Пошто се свака променљива може променити највише \(n\) пута (где је \(n\) неко горње ограничење њихове вредности, обично дужина низа), број промена (па самим тим и извршавања тела петље) је највише \(2n\) и линеаран је по \(n\) тј. сложеност му је \(O(n)\).

Алгоритми засновани на техници два показивача обично могу да се изведу коришћењем одсецања примењених на угнежђене петље, па је, као и код сваке примене одсецања, потребно пажљиво образложити њихову коректност.

Техника два показивача — задаци

Обједињавање

За овај задатак можете видети решење
покушало: 667, решило: 89%

Сортирани квадрати бројева

За овај задатак можете видети решење
покушало: 309, решило: 70%

Заједнички елементи три уређена низа

покушало: 595, решило: 70%

Близанци

покушало: 629, решило: 87%

Прости чиниоци 235

За овај задатак можете видети решење
покушало: 252, решило: 74%

Сегмент датог збира у низу природних бројева

За овај задатак можете видети решење
покушало: 221, решило: 27%

Број сегмената малог збира

покушало: 127, решило: 74%

Кајмак

покушало: 123, решило: 76%

Тастатура и миш

покушало: 294, решило: 75%

Двобојка

За овај задатак можете видети решење
покушало: 160, решило: 92%

Тробојка

За овај задатак можете видети решење
покушало: 109, решило: 91%

Оптимални сервис

покушало: 135, решило: 79%

Два блиска предајника

покушало: 165, решило: 89%

Светиљка

покушало: 103, решило: 75%

Број парова датог збира

покушало: 426, решило: 88%

Тројке датог збира (3sum)

покушало: 228, решило: 88%

Разлика висина

За овај задатак можете видети решење
покушало: 168, решило: 67%

Пуно фигурица

покушало: 308, решило: 70%

Пар производа у ранцу

За овај задатак можете видети решење
покушало: 69, решило: 71%

Број сегмената са различитим елементима

За овај задатак можете видети решење
покушало: 140, решило: 84%

Конференција

покушало: 86, решило: 69%

Најкраћа подниска која садржи све дате карактере

покушало: 181, решило: 83%

Квадратно-троугаони бројеви

покушало: 65, решило: 35%

Кружни пут

За овај задатак можете видети решење
покушало: 71, решило: 83%

Двоструко сортирана претрага

За овај задатак можете видети решење
покушало: 94, решило: 84%